package 动态规划;

import java.util.*;

/**
 * 139. 单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 * 思路：
 *  要判断字符串s是否能被拆分为字典的单词序列，可以使用动态规划来解决。具体步骤如下;
 *  1:预处理：将字典转换为哈希集合以便快速查找，并记录字典中单词的最大长度以优化后续遍历。
 *  2：动态规划数组：定义 dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分。
 *  3：状态转移方程： 对于每个位置i，检查所有可能的拆分位置j（从i往前最多maxLen个字符），若dp[j] 为true且子串s.substring(j, i) 存在于字典中，则 dp[i] 为 true。
 *  4：结果：最终 dp[s.length()] 即为答案。
 *
 */
public class L_139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 通过一个Set集合记录字典列表，方便后续快速查找
        Set<String> wordSet = new HashSet<>(wordDict);
        int maxLen = 0;
        // 记录当前字典中最大的长度，便于后续动态规划方程使用
        for (String word : wordDict){
            maxLen = Math.max(maxLen, word.length());
        }
        int n = s.length();
        // 定义状态转移数组：dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分。
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 初始化 dp[0] 为 true，表示空字符串可以被拆分。

        // 遍历字符串 s，从第一个字符到最后一个字符
        for (int i = 1; i <= n; i++) {
            // 遍历可能的单词长度，最多不能超过maxLen且不能超过i
            for (int k = 1; k <= maxLen && k <= i ; k++) {
                int start = i - k;
                // 只需要找到当前位上存在一种拆分方式，就可以跳出当前循环，进行下一次
                if (dp[start] && wordSet.contains(s.substring(start, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    /**
     * 使用动态规划的解法,思路：
        1：先将单词列表数组转换为字典表，方便后续查找
        2：找到字典表中最长的单词长度，用于后续的状态转移方程
        3：定义状态数组dp[], dp[i] 表示字符串s中的当前i个字符是否可以被拆分，可以被拆分返回true
        4: 状态转移方程定义： 对于当前字符i，可以检查其所有的前缀j开始的字符串情况，（j <= maxLen,下标j距离下标i的间距不超过maxLen）
            如果dp[j] 为true，且 s.substring(j, i) 在字典中存在，则dp[i] 为true
        5: 最终dp[s.length()] 即为结果
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak11(String s, List<String> wordDict) {
        if (s == null || s.length() == 0){
            return true;
        }
        // 创建一个哈希集合，用于快速查找字典中的单词
        Set wordSet = new HashSet<>(wordDict);
        int maxLen = 0;
        // 找到最长的单词长度
        for (String word : wordDict){
            maxLen = Math.max(maxLen, word.length());
        }
        // 定义状态转移数组
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true; // 表示空字符串可以拆分
        for (int i = 1; i <= s.length() ; i++) {
            //遍历当前位置i的所有前缀j的情况，判断当前位置i是否可以被拆分
            for (int j = 1; j <=maxLen && j <= i; j++) {
                int start = i - j;
                // 只要dp[start]为true 且 s.substring(start, i) 在字典中存在，则dp[i]为true
                if (dp[start] && wordSet.contains(s.substring(start, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入字符串：");
        String s = scanner.nextLine();
        System.out.println("请输入单词列表的大小：");
        int size = scanner.nextInt();
        List<String> wordDict = new ArrayList<>();
        System.out.println("请逐个输入单词列表：");
        for (int i = 0; i < size; i++){
            wordDict.add(scanner.next());
        }

        L_139 l_139=new L_139();
        System.out.println(l_139.wordBreak(s, wordDict));
        System.out.println(l_139.wordBreak11(s, wordDict));
    }
}
